package review;

import org.junit.Test;

import java.util.Arrays;

import static sort.util.SortUtil.greater;
import static sort.util.SortUtil.swap;

public class ShellSort {
    @Test
    public void test() {
        Integer[] nums = {5, 2, 7, 4, 1, 3, 8, 9};
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void sort(Comparable[] nums) {
        int len = nums.length;
        int h = 1;
        while (h < len / 2) {   //h不能等于 len/2，否则得到的len值就是len+1了
            h = h * 2 + 1;
        }

        while (h >= 1) {
            for (int i = h; i < len; i++) {
                for (int j = i; j >= h; j -= h) {
                    if (greater(nums[j - h], nums[j])) {
                        swap(nums, j, j - h);
                    }else {
                        break;
                    }
                }
            }
            h /= 2;
        }
    }

}
